import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.fourSumCount(new int[]{1, 2}, new int[]{-2, -1}, new int[]{-1, 2}, new int[]{0, 2}));
        System.out.println(s.fourSumCount(new int[]{0}, new int[]{0}, new int[]{0}, new int[]{0}));
    }
}


class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> sum12Counts = new HashMap<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                sum12Counts.put(num1 + num2, sum12Counts.getOrDefault(num1 + num2, 0) + 1);
            }
        }

        int ans = 0;
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                ans += sum12Counts.getOrDefault(-num3 - num4, 0);
            }
        }

        return ans;
    }
}

//超时
class Solution1 {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Arrays.sort(nums3);
        Arrays.sort(nums4);
        int ans = 0;
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                int i = 0, j = nums4.length - 1;
                int target = -num1 - num2;
                while (i < nums3.length && j >= 0) {
                    int num3 = nums3[i];
                    int num4 = nums4[j];
                    if (num3 + num4 > target) {
                        j--;
                    } else if (num3 + num4 < target) {
                        i++;
                    } else {
                        int countSame3 = 1, countSame4 = 1;
                        while (i + 1 < nums3.length && nums3[i + 1] == nums3[i]) {
                            i++;
                            countSame3++;
                        }
                        while (j - 1 >= 0 && nums4[j - 1] == nums4[j]) {
                            j--;
                            countSame4++;
                        }
                        ans += countSame3 * countSame4;
                        i++;
                        j--;
                    }
                }
            }
        }
        return ans;
    }
}
